import java.util.Arrays;

public class Solution2234 {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        Arrays.sort(flowers);
        int t=flowers.length-1;
        long base=0;
        while (t>=0 && flowers[t]>=target){
            base+=full;
            t--;
        }
        if (t<0){
            return base;
        }
        long[] need=new long[flowers.length];
        for (int i=1;i<=t;i++){
            need[i]=need[i-1]+(flowers[i]-flowers[i-1])*i;
        }
        long max=base+cal(flowers,need,newFlowers,target, partial,t);
        for (int i=t;i>=0;i--){
            if (target-flowers[i]>newFlowers){
                break;
            }
            newFlowers=newFlowers-(target-flowers[i]);
            base+=full;
            max=Math.max(max,base+cal(flowers,need,newFlowers,target, partial,i-1));
        }
        return max;
    }

    private long cal(int[] flowers, long[] need, long newFlowers, int target, int partial, int t) {
        if (t<0){
            return 0;
        }
        int l=0,r=t,ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (need[mid]<=newFlowers){
                ans=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return Math.min((long)flowers[ans]+(newFlowers-need[ans])/Math.min(t+1,ans+1),target-1)*partial;
    }

    public static void main(String[] args) {
        System.out.println(new Solution2234().maximumBeauty(new int[]{10,9,16,14,6,5,11,12,17,2,11,15,1},80,14,15,1));
    }
}
